package com.wyd.tree;


import static java.lang.Math.max;

class AVLNode {
    protected int key;

     protected int balance;

     protected int height;

     public int getHeight() {

         return height;
     }

     public void setHeight(int height) {
         this.height = height;
     }

     public int getBalance() {
         return balance;
     }

     public void setBalance(int balance) {
         this.balance = balance;
     }

     protected AVLNode left;

     protected AVLNode right;

    public int getKey() {
        return key;
    }

    public void setKey(int key) {
        this.key = key;
    }


    public AVLNode getLeft() {
        return left;
    }

    public void setLeft(AVLNode left) {
        this.left = left;
    }

    public AVLNode getRight() {
        return right;
    }

    public void setRight(AVLNode right) {
        this.right = right;
    }
    public int heigh(){
        return heigh(this);
    }

    public int heigh(AVLNode node){
        if(node==null){
            return 0; //递归结束，空子树高度为0
        }else{
            //递归获取左子树高度
            int l = heigh(node.getLeft());
            //递归获取右子树高度
            int r = heigh(node.getRight());
            //高度应该算更高的一边，（+1是因为要算上自身这一层）
            return l>r? (l+1):(r+1);
        }
    }

}
public class AVLTree {
    public int getHeght(AVLNode node){
        if(node==null){
            return 0; //递归结束，空子树高度为0
        }else{
            //递归获取左子树高度

            //高度应该算更高的一边，（+1是因为要算上自身这一层）
            return node.heigh();
        }
    }
    public int heigh(AVLNode node){
        if(node==null){
            return 0; //递归结束，空子树高度为0
        }else{
            //递归获取左子树高度
            int l = heigh(node.getLeft());
            //递归获取右子树高度
            int r = heigh(node.getRight());
            //高度应该算更高的一边，（+1是因为要算上自身这一层）
            return l>r? (l+1):(r+1);
        }
    }
    private AVLNode root;

    public AVLTree(AVLNode root) {
        this.root = root;
    }

    public AVLTree() {
    }

    public AVLNode getRoot() {
        return root;
    }
    public int heigh(){
        return getRoot().heigh();
    }


    public AVLNode insert(AVLNode node,int key){
//        if (root == null){
//            AVLNode p = new AVLNode();
//            p.setKey(key);
//            this.root = p;
//            return p;
//        }
            if (node == null){
                AVLNode p = new AVLNode();
                p.setKey(key);
                return p;
            }

            if (key < node.key){
                node.left = insert(node.left,key);
            }
            if (key > node.key){
                node.right = insert(node.right,key);
            }
            if (key == node.key){
                return node;
            }

//            if () {
//                return node;
//            }
//        System.out.println("sfdsdfsd");
//                 printTree(root, 0);
            int leftH = getHeght(node.getLeft());
            int right = getHeght(node.right);

            node.setHeight(1 +(max(leftH,right)));

            int bl = leftH - right;

            // 当 平衡值 大于 1  和小于 -1 时候需要做平衡操作

           if(bl >1 ){
                // 左边大于右边
               // 分为 LL 和LR 情况
               // LL 左孩子的左树不平衡
               // LR 左孩子的 右树不平衡

               // LL
               if (key < node.left.key){
                    // 右旋
                 return   rightRotate(node);
               }
                // LR
               if (key > node.left.key){
                   // 先左旋 后右
                   node.left = leftRotate(node.left);

                   return   rightRotate(node);

               }
           }
        if(bl < -1 ){
            // 左边大于右边
            // 分为 LL 和LR 情况
            // LL 左孩子的左树不平衡
            // LR 左孩子的 右树不平衡

            // RR
            if (key > node.right.key){
                // 右旋
                return   leftRotate(node);
            }
            // RL
            if (key < node.right.key){
                // 先左旋 后右
                node.right = rightRotate(node.right);

                return   leftRotate(node);

            }
        }

            return node;

    }

    AVLNode rightRotate(AVLNode y) {
        AVLNode x = y.left;
        AVLNode T2 = x.right;

        x.right = y;
        y.left = T2;

        y.height = max(heigh(y.left), heigh(y.right)) + 1;
        x.height = max(heigh(x.left), heigh(x.right)) + 1;

        return x;
    }

    AVLNode leftRotate(AVLNode x) {
        AVLNode y = x.right;
        AVLNode T2 = y.left;

        y.left = x;
        x.right = T2;

        x.height = max(heigh(x.left), heigh(x.right)) + 1;
        y.height = max(heigh(y.left), heigh(y.right)) + 1;

        return y;
    }



    public void printTree(AVLNode node, int level) {
        if (node == null) {
            return;
        }


        printTree(node.getRight(), level + 1);
        if (level != 0) {
            for (int i = 0; i < level - 1; i++)
            {
                System.out.print("|\t");
            }
            System.out.println("|-------" + node.getKey() +"("+node.getBalance()+")");
        } else {
            System.out.println(node.getKey()+"("+node.getBalance()+")");

        }

        printTree(node.getLeft(), level + 1);
    }

    private int combl(AVLNode node){
        if (node == null) {
            return 0;
        }

        int leftBl = heigh(node.getLeft());
        int right = heigh(node.getRight());
        int bl =  leftBl - right;
        node.setBalance(bl);
        combl(node.getLeft());

        combl(node.getRight());
        return bl;
    }

    public static void main(String[] args) {
        AVLTree binaryTree = new AVLTree();

        binaryTree.root = binaryTree.insert(binaryTree.getRoot(), 10);

        binaryTree.root = binaryTree.insert(binaryTree.getRoot(),2);
//        binaryTree.root = binaryTree.printTree(binaryTree.root, 0);

        binaryTree.root = binaryTree.insert(binaryTree.getRoot(),1);
        binaryTree.root = binaryTree.insert(binaryTree.getRoot(),4);
        binaryTree.root =binaryTree.insert(binaryTree.getRoot(),3);
        binaryTree.root =binaryTree.insert(binaryTree.getRoot(),12);
        binaryTree.root = binaryTree.insert(binaryTree.getRoot(),11);

        binaryTree.root = binaryTree.insert(binaryTree.getRoot(),13);
        binaryTree.root = binaryTree.insert(binaryTree.getRoot(),14);

        binaryTree.root =binaryTree.insert(binaryTree.getRoot(),18);
//
//        binaryTree.combl(binaryTree.getRoot());


        binaryTree.printTree(binaryTree.root, 0);



    }

}
